1302. Почти простые числа
Натуральное
число называется почти простым, если оно не простое и имеет только один простой
делитель. Найти количество почти простых чисел в заданном интервале натуральных
чисел.
Вход. Первая строка содержит количество
тестов n (n £ 600).
Каждая следующая строка является отдельным тестом и содержит два числа low
и high (0 < low £ high
< 1012).
Выход. Для
каждого теста вывести в отдельной строке количество почти простых чисел в
промежутке [low.. high] включительно.
|
Пример входа |
Пример выхода |
31 101 20
1 5 |
3 4 1 |
РЕШЕНИЕ
решето
Эратосфена - бинарный поиск
Анализ алгоритма
Почти простые числа имеют вид pk, где p – простое число, k ³ 2. Например,
почти простыми будут 4, 8, 16, 32, 9, 81, … . Поскольку high < 1012,
то исходя из определения почти простого числа p < 106.
Сгенерируем массив primes длины 1000000 = 106, для которого primes[i]
= 1 если i – простое число и
primes[i] = 0 иначе. Далее сгенерируем и отсортируем в массиве m
все почти простые числа (их будет 80070).
Обозначим через f(a, b) количество почти
простых чисел в промежутке [a..b]. Тогда
f(low, high) = f(1,
high) – f(1, low – 1)
Количество почти простых чисел на промежутке [1 .. n]
равно номеру места (индексу), куда можно вставить число n в
отсортированный массив m по верхней границе с учетом сохранения
упорядоченности. Номер индекса ищется бинарным поиском по массиву m при
помощи функции upper_bound.
Пример
Сгенерируем все
почти простые числа в промежутке от 1 до 100. Сначала запишем степени 2, не
большие 100. Потом степени 3, 5, 7. Квадрат числа 11 уже больше 100, поэтому
степеней 11 среди почти простых чисел в интервале [1..100] не будет.
Отсортируем
массив:
Рассмотрим
второй тест. От 1 до 20 находится 4 почти простых числа: 4, 8, 9, 16.
Реализация
алгоритма
Объявим глобальные массивы. Почти простые числа до 1012 являются степенями простых до MAX = 106. Почти простые числа сохраняем в массиве m.
#define MAX 1000010
char primes[MAX];
long long
m[MAX];
Сгенерируем
массив primes для тестирования чисел
на простоту.
void gen_primes(void)
{
int i, j;
for(i = 0; i
< MAX; i++) primes[i] = 1;
for(i = 2; i
< sqrt(MAX); i++)
if
(primes[i])
for(j = i
* i; j < MAX; j += i) primes[j] = 0;
}
Основная часть
программы.
gen_primes();
Для каждого
простого числа i заносим в массив m числа i2, i3,
i4, … пока очередная степень не станет больше 1012.
Переменная ptr содержит количество почти
простых чисел, занесенных в массив m. Поскольку почти простые числа
ограничены значением 1012, то работать следует с 64 битовыми целыми
числами (тип long long).
for(i = 2; i < MAX; i++)
if
(primes[i])
{
long long temp = 1LL*i*i;
while(temp
< 1LL*MAX*MAX)
{
m[ptr++] = temp;
temp *= i;
}
}
Сортируем массив
m, используя STL:
sort(m,m+ptr);
Читаем
количество входных тестов tests и для каждого интервала [l, h]
вычисляем и выводим значение f(l, h) = f(1, h) – f(1, l
– 1) за время O(log2 ptr).
scanf("%d", &tests);
while(tests--)
{
scanf("%lld
%lld", &l, &h);
printf("%d\n",
upper_bound(m,m+ptr,h) - upper_bound(m,m+ptr,l-1));
}
Java реализация
import java.util.*;
public class Main
{
public static ArrayList<Long> primes = new ArrayList<Long>();
public static void GenPrimes()
{
final int MAX_SIZE = 1000001;
BitSet bits = new BitSet(MAX_SIZE);
bits.set(2, MAX_SIZE, true);
for (int i = 2; i < Math.sqrt(MAX_SIZE); i++)
{
if (bits.get(i))
for (int j = i * i; j < MAX_SIZE; j += i)
bits.set(j, false);
}
for (int i = 2; i < MAX_SIZE; i++)
if (bits.get(i))
{
long temp = i;
while ((temp *= i) < 1000000000000L)
primes.add(temp);
}
primes.add(1000000000001L);
Collections.sort(primes);
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int tests = con.nextInt();
GenPrimes();
for(int i = 0; i < tests; i++)
{
Long low = con.nextLong();
Long high = con.nextLong();
int lIndex = Collections.binarySearch(primes, low);
if (lIndex < 0) lIndex = -(lIndex + 1);
int hIndex = Collections.binarySearch(primes, high);
if (hIndex < 0) hIndex = -(hIndex + 1); else hIndex++;
System.out.println(hIndex - lIndex);
}
}
}